package com.hr.剑指offer.work1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 周恒哲
 * @date 2020/06/12
 **/
public class 面试题13_机器人的运动范围 {
    //避免递归传参，定义全局变量
    int m;
    int n;
    int k;
    //是否已经访问过
    boolean[][] visited;
    /**
     * 深度优先搜索（DFS）
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int movingCount(int m, int n, int k) {
        this.m=m;
        this.n=n;
        this.k=k;
        this.visited=new boolean[m][n];
        return dfs(0,0,0,0);
    }

    private int dfs(int x, int y, int sx, int sy) {
        //下标越界，数位和大于指定值以及已经访问过都会直接返回
        if (x>=m || y>=n || k < sx+sy || visited[x][y]){
            return 0;
        }
        //标记此坐标访问过
        visited[x][y]=true;
        //适用范围是[0,100)
        // 1.当x或者y从n9进位成(n+1)0时，数位和减小了8
        //    设进位后数的数位和为n，差值为x，得出方程n=(n-1)+9+x，即x=-8
        // 2.当x或者y在个位数从0到8的范围内加1时，数位和增加了1，这是常识。
        //至于为什么只向右和向下扩张是因为不用回溯已走过的路径，扩张的路径只会向下或者向右
        return 1 + dfs(x + 1, y, (x + 1) % 10 != 0 ? sx + 1 : sx - 8, sy) + dfs(x, y + 1, sx, (y + 1) % 10 != 0 ? sy + 1 : sy - 8);
    }


    /**
     * 广度优先搜索（BFS）
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int movingCount2(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        Queue<int[]> queue= new LinkedList<int[]>();
        queue.add(new int[] { 0, 0, 0, 0 });
        while(queue.size() > 0) {
            int[] x = queue.poll();
            int i = x[0], j = x[1], si = x[2], sj = x[3];
            if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
            visited[i][j] = true;
            res ++;
            queue.add(new int[] { i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
            queue.add(new int[] { i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
        }
        return res;
    }
}
